The practical application of graph prime factorization algorithms is limitedin practice by unavoidable noise in the data. A first step towardserror-tolerant "approximate" prime factorization, is the development of localapproaches that cover the graph by factorizable patches and then use thisinformation to derive global factors. We present here a local, quasi-linear al-gorithm for the prime factorization of "locally unrefined" graphs with respectto the strong product. To this end we introduce the backbone B(G) for a givengraph G and show that the neighborhoods of the backbone vertices provide enoughinformation to determine the global prime factors.
展开▼
